package algorithmTopics.link;

import java.util.Arrays;

public class test4 {


    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        ListNode listNode1 = new ListNode(2);
        listNode.next = listNode1;
        ListNode listNode2 = new ListNode(3);
        listNode1.next = listNode2;
        System.out.println(Arrays.toString(printLink(listNode, null)));

        test4 test2 = new test4();

        System.out.println(Arrays.toString(printLink(test2.mergeTwoLists(listNode,listNode),null)));

    }



    //构造链表
    public static class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }

   //合并 排序两个链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
       //新的链表来存贮合并之后的
        ListNode res = new ListNode(0);
        ListNode curr = res;
        //把较小的数字放进去即可
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                curr.next = list1;
                list1 = list1.next;
            }else{
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;

        }
        curr.next = list1 == null ? list2:list1;

        return res.next;
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        //获取长度
        int linkLen = getLinkLen(head) - n;
        //删除头节点
        if (linkLen == 0) {
            return head.next;
        }
        //需要删除节点的前一位
        ListNode node = head;
        for (int i = 0; i < linkLen - 1; i++) {
            node = node.next;
        }
        node.next = node.next.next;
        return head;
    }

    //获取链表长度
    public int getLinkLen(ListNode head) {
        if (head.next == null) {
            return 1;
        }
        int i = getLinkLen(head.next);
        return  i + 1;
    }

    //打印链表
    public static int[] printLink(ListNode head , int[] list ) {
        if (head.next == null) {
            return new int[] {head.val};
        }
        int[] ints = printLink(head.next, null);
        //结果集合
        int[] res = new int[ints.length + 1];
        System.arraycopy(ints,0,res,0,ints.length);
        res[ints.length] = head.val;
        return res;

    }

    //反转链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //当前节点
        ListNode curr = head.next;
        //头节点指向变为空
        head.next = null;
        //前一位节点
        ListNode pre = head;
        //循环到最后一位
        while (curr.next != null) {
            //存储当前节点的下一位节点
            ListNode temp = curr.next;
            //当前节点指向前一位
            curr.next = pre;
            //前一位变为当前，当前变为后面
            pre = curr;
            curr = temp;

        }
        curr.next = pre;
        return curr;
    }


}
